import random


def generate_array(n, method=None):
    """根据状态生成数组"""
    # 生成一个包含1到n的唯一整数数组
    states = [
        "unordered",
        "ascend",
        "descend",
        "ascend_then_descend",
        "descend_then_ascend",
    ]
    state = states[method]
    arr = random.sample(range(0, n * 10), n)

    if state == "ascend":  # 升序
        arr.sort()
    elif state == "descend":  # 降序
        arr.sort(reverse=True)
    elif state == "ascend_then_descend":  # 先升后降
        arr.sort()  # 先升序
        mid = len(arr) // 2
        arr[mid:] = arr[mid:][::-1]  # 后半部分逆序
    elif state == "descend_then_ascend":  # 先降后升
        arr.sort(reverse=True)  # 先降序
        mid = len(arr) // 2
        arr[mid:] = arr[mid:][::-1]  # 后半部分逆序
    else:  # 未排序
        random.shuffle(arr)

    return arr


def check_array_up(arr):
    n = 0
    for i in range(1, len(arr)):
        if arr[i] > arr[i - 1]:
            n += 1
        else:
            return n
    return n


def check_array_down(arr):
    n = 0
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            n += 1
        else:
            return n
    return n


def check_array_order(arr):
    """
    判断数组排序状态。
    返回值：
        0：未排序
        1：升序
        2：降序
        3：先升后降
        4：先降后升
    """
    n = len(arr)
    if n <= 1:
        return 1  # 单元素或空数组视为升序
    if arr[1] > arr[0]:
        up = check_array_up(arr)
        down = check_array_down(arr[up:])
        if up == n - 1:  # 升序
            return 1
        elif down + up == n - 1:  # 先升后降
            return 3
        else:  # 未排序
            return 0
    else:
        down = check_array_down(arr)
        up = check_array_up(arr[down:])
        if down == n - 1:  # 降序
            return 2
        elif down + up == n - 1:  # 先降后升
            return 4
        else:  # 未排序
            return 0


def sequential_search(arr, target):
    comparison_count = 0  # 统计比较次数
    for i in arr:
        comparison_count += 1  # 每次比较都加1
        if i == target:
            return True, comparison_count  # 找到目标元素，返回True和比较次数
    return False, comparison_count  # 未找到目标元素，返回False和比较次数


# 顺序查找
def linear_search(arr, target):
    comparison_count = 0
    status = check_array_order(arr)
    if status == 1:  # 升序
        for index, value in enumerate(arr):
            comparison_count += 1
            if value == target:
                return (
                    True,
                    index,
                    comparison_count,
                )  # 找到该元素，返回元素位置及比较次数
            elif value > target:
                if index == 0:  # 如果目标值比第一个元素还小
                    return [False, index, value, comparison_count]
                elif value - target > target - arr[index - 1]:
                    return [
                        False,
                        index - 1,
                        arr[index - 1],
                        comparison_count,
                    ]  # 未找到该元素，返回最接近该元素的元素值，元素位置及比较次数
                else:
                    return [False, index, value, comparison_count]
            elif value < target and index == len(arr) - 1:
                return [False, index, value, comparison_count]
    elif status == 2:  # 降序
        for index, value in enumerate(arr):
            comparison_count += 1
            if value == target:
                return (
                    True,
                    index,
                    comparison_count,
                )  # 找到该元素，返回元素位置及比较次数
            elif value < target:
                if index == 0:  # 如果目标值比第一个元素还大（降序数组）
                    return [False, index, value, comparison_count]
                elif abs(value - target) > abs(target - arr[index - 1]):
                    return (
                        False,
                        index - 1,
                        arr[index - 1],
                        comparison_count,
                    )  # 未找到该元素，返回最接近该元素的元素值，元素位置及比较次数
                else:
                    return [False, index, value, comparison_count]
            elif value > target and index == len(arr) - 1:
                return [False, index, value, comparison_count]
    else:
        return False, "数组类型不符合条件，请重新生成一个升序或降序的数组"


# 二分查找
def binary_search(arr, target):
    comparison_count = 0
    status = check_array_order(arr)

    if status == 1:  # 升序数组
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            comparison_count += 1
            if arr[mid] == target:
                return True, mid, comparison_count  # 找到目标值
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        # 未找到目标值，找到最接近的元素
        closest_index = right if right >= 0 else left
        closest_value = arr[closest_index]
        if left >= len(arr):
            return [False, closest_index, closest_value, comparison_count]
        elif right < 0:
            return [False, closest_index, closest_value, comparison_count]
        else:
            # 判断最近的元素是 left 还是 right
            if abs(arr[left] - target) < abs(arr[right] - target):
                closest_index = left
            return [False, closest_index, arr[closest_index], comparison_count]

    elif status == 2:  # 降序数组
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            comparison_count += 1
            if arr[mid] == target:
                return True, mid, comparison_count  # 找到目标值
            elif arr[mid] > target:
                left = mid + 1
            else:
                right = mid - 1

        # 未找到目标值，找到最接近的元素
        closest_index = right if right >= 0 else left
        closest_value = arr[closest_index]
        if left >= len(arr):
            return [False, closest_index, closest_value, comparison_count]
        elif right < 0:
            return [False, closest_index, closest_value, comparison_count]
        else:
            # 判断最近的元素是 left 还是 right
            if abs(arr[left] - target) < abs(arr[right] - target):
                closest_index = left
            return [False, closest_index, arr[closest_index], comparison_count]

    else:
        return False, "数组类型不符合条件，请重新生成一个升序或降序的数组"


# 三分查找
def ternary_search(arr, target):
    comparison_count = 0
    status = check_array_order(arr)

    if status == 1:  # 升序
        left, right = 0, len(arr) - 1
        while right >= left:
            mid1 = left + (right - left) // 3
            mid2 = right - (right - left) // 3
            comparison_count += 2

            if arr[mid1] == target:
                return True, mid1, comparison_count
            elif arr[mid2] == target:
                return True, mid2, comparison_count

            if target < arr[mid1]:
                right = mid1 - 1
            elif target > arr[mid2]:
                left = mid2 + 1
            else:
                left = mid1 + 1
                right = mid2 - 1

        # 找不到时返回最接近的元素
        if left >= len(arr):
            return False, right, arr[right], comparison_count
        elif right < 0:
            return False, left, arr[left], comparison_count
        else:
            if abs(arr[left] - target) < abs(arr[right] - target):
                return False, left, arr[left], comparison_count
            else:
                return False, right, arr[right], comparison_count
    elif status == 2:  # 降序
        left, right = 0, len(arr) - 1
        while right >= left:
            mid1 = left + (right - left) // 3
            mid2 = right - (right - left) // 3
            comparison_count += 2

            if arr[mid1] == target:
                return True, mid1, comparison_count
            elif arr[mid2] == target:
                return True, mid2, comparison_count

            if target > arr[mid1]:
                right = mid1 - 1
            elif target < arr[mid2]:
                left = mid2 + 1
            else:
                left = mid1 + 1
                right = mid2 - 1

        # 找不到时返回最接近的元素
        if left >= len(arr):
            return False, right, arr[right], comparison_count
        elif right < 0:
            return False, left, arr[left], comparison_count
        else:
            if abs(arr[left] - target) < abs(arr[right] - target):
                return False, left, arr[left], comparison_count
            else:
                return False, right, arr[right], comparison_count
    else:
        return False, "数组类型不符合条件，请重新生成一个升序或降序的数组"


# 插值查找
def interpolation_search(arr, target):
    comparison_count = 0
    status = check_array_order(arr)

    if status == 1:  # 升序
        left, right = 0, len(arr) - 1
        while left <= right and arr[left] != arr[right]:
            # 插值公式计算中间位置
            mid = left + (right - left) * (target - arr[left]) // (
                arr[right] - arr[left]
            )
            comparison_count += 1

            if mid < left or mid > right:
                break  # 防止越界

            if arr[mid] == target:
                return True, mid, comparison_count
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        # 找不到时返回最接近的元素
        if left >= len(arr):
            return False, right, arr[right], comparison_count
        elif right < 0:
            return False, left, arr[left], comparison_count
        else:
            if abs(arr[left] - target) < abs(arr[right] - target):
                return False, left, arr[left], comparison_count
            else:
                return False, right, arr[right], comparison_count
    elif status == 2:  # 降序
        left, right = 0, len(arr) - 1
        while left <= right and arr[left] != arr[right]:
            # 插值公式计算中间位置
            mid = left + (right - left) * (arr[left] - target) // (
                arr[left] - arr[right]
            )
            comparison_count += 1

            if mid < left or mid > right:
                break  # 防止越界

            if arr[mid] == target:
                return True, mid, comparison_count
            elif arr[mid] > target:
                left = mid + 1
            else:
                right = mid - 1

        # 找不到时返回最接近的元素
        if left >= len(arr):
            return False, right, arr[right], comparison_count
        elif right < 0:
            return False, left, arr[left], comparison_count
        else:
            if abs(arr[left] - target) < abs(arr[right] - target):
                return False, left, arr[left], comparison_count
            else:
                return False, right, arr[right], comparison_count
    else:
        return False, "数组类型不符合条件，请重新生成一个升序或降序的数组"


# 先升后降二分查找
def find_peak_binary(arr):
    comparisons = 0
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        comparisons += 1
        if arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return arr[left], comparisons


# 先升后降三分查找
def find_peak_ternary(arr):
    comparisons = 0
    left, right = 0, len(arr) - 1
    while right - left > 1:
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        comparisons += 1
        if arr[mid1] < arr[mid2]:
            left = mid1 + 1
        else:
            right = mid2 - 1
    # 最后在剩余的三元素中找最大值
    peak = max(arr[left : right + 1])
    comparisons += right - left
    return peak, comparisons


# 先降后升二分查找
def find_min_binary(arr):
    comparisons = 0
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        comparisons += 1
        if arr[mid] > arr[mid + 1]:  # 判断是否右侧更小
            left = mid + 1
        else:
            right = mid  # 包含当前 mid
    return arr[left], comparisons


# 先降后升三分查找
def find_min_ternary(arr):
    comparisons = 0
    left, right = 0, len(arr) - 1
    while right - left > 1:
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        comparisons += 1
        if arr[mid1] > arr[mid2]:  # 判断右侧是否更小
            left = mid1 + 1
        else:
            right = mid2 - 1
    # 最后在剩余的三元素中找最小值
    min_value = min(arr[left : right + 1])
    comparisons += right - left
    return min_value, comparisons


def kth_smallest_brute_force(arr, k):
    global min_val
    comparisons = 0
    used = [False] * len(arr)
    for _ in range(k):
        min_val = float("inf")
        min_idx = -1
        for i in range(len(arr)):
            if not used[i]:
                comparisons += 1
                if arr[i] < min_val:
                    min_val = arr[i]
                    min_idx = i
        used[min_idx] = True
    return min_val, comparisons


def kth_smallest_sorted(arr, k):
    comparisons = 0

    def merge_sort(arr):
        nonlocal comparisons
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])
        sorted_arr = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons += 1
            if left[i] < right[j]:
                sorted_arr.append(left[i])
                i += 1
            else:
                sorted_arr.append(right[j])
                j += 1
        sorted_arr.extend(left[i:])
        sorted_arr.extend(right[j:])
        return sorted_arr

    sorted_arr = merge_sort(arr)
    return sorted_arr[k - 1], comparisons


def kth_smallest_quickselect(arr, k):
    comparisons = 0

    def partition(low, high):
        nonlocal comparisons
        pivot = arr[high]
        i = low
        for j in range(low, high):
            comparisons += 1
            if arr[j] < pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]
        return i

    def quickselect(low, high, k):
        if low == high:
            return arr[low]
        pivot_index = random.randint(low, high)
        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
        partition_index = partition(low, high)
        if k == partition_index:
            return arr[k]
        elif k < partition_index:
            return quickselect(low, partition_index - 1, k)
        else:
            return quickselect(partition_index + 1, high, k)

    result = quickselect(0, len(arr) - 1, k - 1)
    return result, comparisons


# if __name__ == "__main__":
#     arr = [3, 2, 1]
#     k = 2
#     if k > len(arr):
#         print(f"需要寻找的第{k}小元素超出数组范围，请重新输入")
#     else:
#         # 蛮力法
#         result_brute, comp_brute = kth_smallest_brute_force(arr.copy(), k)
#         print(f"蛮力法: 第{k}小元素是 {result_brute}, 比较次数为: {comp_brute}次")
#
#         # 预排序法
#         result_sorted, comp_sorted = kth_smallest_sorted(arr.copy(), k)
#         print(f"预排序法（预排序采用二分查找法）: 第{k}小元素是 {result_sorted}, 比较次数为: {comp_sorted}次")
#
#         # 减可变规模法
#         result_quick, comp_quick = kth_smallest_quickselect(arr.copy(), k)
#         print(f"减可变规模法（采用快速选择法）: 第{k}小元素是 {result_quick}, 比较次数为: {comp_quick}次")


if __name__ == "__main__":
    arr = [11, 14, 27, 31, 33, 69, 77, 78, 86, 97]
    target = 10
    if linear_search(arr, target)[0] == True:
        index, comparison_count = (
            linear_search(arr, target)[1],
            linear_search(arr, target)[2],
        )
        print(f"找到元素{target}，索引为：{index}，比较次数为：{comparison_count}次")
    else:
        index, item, comparison_count = (
            linear_search(arr, target)[1],
            linear_search(arr, target)[2],
            linear_search(arr, target)[3],
        )
        print(
            f"未找到元素{target}，最接近{target}的元素为：{item}，索引为：{index}，比较次数为：{comparison_count}次"
        )
